A spatial or geographic database can include data concerning locations of features in space or on a surface. Spatial data can include geometric data that includes simple primitive elements such as lines, curves, polygons (with and without holes), and compound elements that are made up of a combination of the primitive elements. For example, a geographical database can include data concerning the location of various objects in a region. Along these lines, a geographic database can include mathematical representations of counties, cities, homes, apartment buildings, parks, businesses, subway stations, and other features. The location information could be in the form of latitude and longitude data or other data that defines position.
Once a database including this information is created it is typically desired to access and utilize the information. One way that the information in the databases is utilized involves determining the relative positions of particular locations. Along these lines, a person might want to find certain types of businesses in a zip code region. At times, it may be desirable to generally determine whether objects in a database have overlapping locations and, if so, the extent of the overlap.
Analyses such as those described above on data in spatial and/or geographic databases can present a number of problems. Determining relationships among data in a database can overtax memory and computing power, take an unacceptable period of time or cost an unacceptable amount of money. This is especially true with data in geographic databases.
For example, one problem concerning trying to determine whether objects have overlapping locations involves actually comparing the outlines of the objects to see if any interactions exist. However, carrying out a point-by-point comparison of two geometries typically requires quite a long time, in some cases, on the order of minutes and, in extreme cases, hours.
Spatial indexes are used by spatial databases (databases which store information related to objects in space) to optimize spatial queries. Indexes used by non-spatial databases cannot effectively handle spatial data features such as how far apart two points are and whether points fall within a spatial area of interest. Thus, other indexing techniques have been developed for spatial data. Common spatial indexing methods include an R-tree. In an R-tree, objects (shapes, lines and points) are grouped using minimum bounding rectangles (MBR). Objects are added to an MBR within the index that will lead to the smallest increase in its size. A hierarchy of MBRs is constructed in which child MBRs descend from a parent MBR that contains them. The index is stored as a set of node entries, with each entry storing coordinates of its associated MBR as well as an identifier that links the MBR to at least one child node.